package Demo01;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {

}

//        //统计字母之前出现的一次当时的字符串长度
//        int[] arr = new int[26];
//        int sup = 1;
//        int count = 0;
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            sup *= 2;
//
//            arr[c-'a'] = sup;
//        }
class Solution {
    public static void main(String[] args) {
        System.out.println(distinctSubseqII("abaa"));
    }

    //    public static int distinctSubseqII(String s) {
//        Set<String> set = new HashSet<>();
//        String[] arr = new String[1];
//        arr[0] = "";
//        final int MOD = 1000000007;
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            int l = arr.length;
//            for (int j = 0; j < l; j++) {
//                String acp = c+arr[j];
//                if(!set.contains(acp)) {
//                    int index = arr.length;
//                    arr = Arrays.copyOf(arr, arr.length+1);
//                    arr[index] = acp;
//                    set.add(acp);
//                }
//            }
//        }
//        return set.size()%MOD;
//    }
    public static int distinctSubseqII(String s) {
        int mod = 1000000007;
        //上次该字符处理的数量
        int[] arr = new int[26];
        //当前该字符处理的数量
        int all = 1;
        int newAdd = 1;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            int tmp = all;
            int a = (all - arr[c - 'a'] + mod) % mod;
            all = (a + all) % mod;
            arr[c - 'a'] = tmp;
        }

        return (all - 1 + mod)%mod;
    }
}